package q795_numSubarrayBoundedMax;

public class Solution {
    /*
    前缀和的标准题
    可以参考
    467. 环绕字符串中唯一的子字符串(中等)
    795. 区间子数组个数(中等)
    904. 水果成篮(中等)
    992. K 个不同整数的子数组（困难）
    1109. 航班预订统计(中等)
     */

    /*
    此题的思路在于拆分步骤：
    要判断一个子集中有一个恰好在范围内的数且所有数不大于right 是相对比较复杂的 需要记录当前滑动窗口的各个属性情况
    但是判断一个子集中有一个小于等于某范围的数是很容易的 也就是下面的lowerCount()函数
    只要当前数字小于max 就不停的增加temp 也就是增加子集长度 然后加入到count中
    例如 2 3 4 1 我们关注小于3的子集 即为 2 3 23 1 共4个

    利用lowerCount(nums, right) - lowerCount(nums, left - 1)就可以得到
    最大值为right的子集 和最大值为left - 1的子集 两者相减所得到的子集中
    至少会有一个会在范围内的数 也就得到了答案
     */
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        return lowerCount(nums, right) - lowerCount(nums, left - 1);
    }

    private int lowerCount(int[] nums, int maxVal) {
        int count = 0, temp = 0;
        for (int num : nums) {
            if (num <= maxVal) {
                temp++;
            }else {
                temp = 0;
            }
            count += temp;
        }
        return count;
    }
}
